package 栈;
import java.util.*;

/**
 * 该类用于计算每日温度，返回需要等待的天数。
 * 时间复杂度：O(n)，空间复杂度：O(n)
 */
public class dailyTemperatures {
    /**
     * 计算每日温度，返回需要等待的天数。
     * 该方法使用单调栈来维护递减的温度，通过比较当前温度与栈顶温度来计算等待天数。
     * @param temp 表示每日温度的数组
     * @return 需要等待的天数数组
     */
    public int[] dailyTemp(int[] temp) {
        ArrayDeque<Integer> stack = new ArrayDeque<>(); // 创建一个栈来存储温度索引
        int[] res = new int[temp.length]; // 初始化结果数组
        for(int i = 0; i < temp.length; i++) { // 遍历温度数组
            while(!stack.isEmpty() && temp[i] > temp[stack.peek()]) { // 当栈不为空且当前温度大于栈顶温度时
                int p = stack.pop(); // 弹出栈顶索引
                res[p] = i - p; // 计算等待天数
            }
            stack.push(i); // 将当前索引入栈
        }
        return res; // 返回结果数组
    }

    /**
     * 主方法，处理输入并输出结果。
     * 该方法从标准输入读取温度数组，并输出需要等待的天数。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建扫描器对象
        String[] s = sc.nextLine().split(","); // 读取温度数组
        int[] temp = new int[s.length]; // 创建温度数组
        for(int i = 0; i < s.length; i++) {
            temp[i] = Integer.parseInt(s[i]); // 解析温度数组
        }
        dailyTemperatures dt = new dailyTemperatures(); // 创建对象
        System.out.println(Arrays.toString(dt.dailyTemp(temp))); // 输出需要等待的天数
        sc.close(); // 关闭扫描器
    }
}
